package _dp_base;

import java.util.Arrays;

/**
 * 322. 零钱兑换
 */
public class No322 {
    private int[] coins;
    private int[][] cache;

    /**
     * 1. 递归搜索 + 保存计算结果 = 记忆化搜索
     */
    public int coinChange1(int[] coins, int amount) {
        this.coins = coins;
        int n = coins.length;
        cache = new int[n][amount + 1];
        for (int[] ints : cache) {
            Arrays.fill(ints, -1);
        }
        int answer = dfs(n - 1, amount);
        return answer == Integer.MAX_VALUE / 2 ? -1 : answer;
    }

    private int dfs(int i, int c) {
        if (i < 0) return c == 0 ? 0 : Integer.MAX_VALUE / 2;
        else if (cache[i][c] != -1) return cache[i][c];
        else if (c < coins[i]) return cache[i][c] = dfs(i - 1, c);
        else return cache[i][c] = Math.min(dfs(i - 1, c), dfs(i, c - coins[i]) + 1);
    }

    /**
     * 2. 一比一翻译成递推
     */
    public int coinChange2(int[] coins, int amount) {
        int n = coins.length;
        int[][] f = new int[n + 1][amount + 1];
        Arrays.fill(f[0], Integer.MAX_VALUE / 2);
        f[0][0] = 0;
        for (int i = 0; i < n; i++) {
            for (int c = 0; c < amount + 1; c++) {
                if (c < coins[i]) f[i + 1][c] = f[i][c];
                else f[i + 1][c] = Math.min(f[i][c], f[i + 1][c - coins[i]] + 1);
            }
        }
        int answer = f[n][amount];
        return answer == Integer.MAX_VALUE / 2 ? -1 : answer;
    }

    /**
     * 3. 空间优化：两个数组（滚动数组）
     */
    public int coinChange3(int[] coins, int amount) {
        int n = coins.length;
        int[][] f = new int[2][amount + 1];
        Arrays.fill(f[0], Integer.MAX_VALUE / 2);
        f[0][0] = 0;
        for (int i = 0; i < n; i++) {
            for (int c = 0; c < amount + 1; c++) {
                if (c < coins[i]) f[(i + 1) % 2][c] = f[i % 2][c];
                else f[(i + 1) % 2][c] = Math.min(f[i % 2][c], f[(i + 1) % 2][c - coins[i]] + 1);
            }
        }
        int answer = f[n % 2][amount];
        return answer == Integer.MAX_VALUE / 2 ? -1 : answer;
    }

    /**
     * 4. 空间优化：一个数组
     */
    public int coinChange4(int[] coins, int amount) {
        int[] f = new int[amount + 1];
        Arrays.fill(f, Integer.MAX_VALUE / 2);
        f[0] = 0;
        for (int coin : coins) {
            for (int c = coin; c < amount + 1; c++) {
                f[c] = Math.min(f[c], f[c - coin] + 1);
            }
        }
        int answer = f[amount];
        return answer == Integer.MAX_VALUE / 2 ? -1 : answer;
    }
}
